#ifndef TEST
#include "test.cpp"
#endif
#ifndef DS
#include "ds.cpp"
#endif

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

namespace TestTestFile
{
    // void Test()
    // {
    //     vector<int> arr = GenerateRandIntArr(100, 10, 30);
    //     cout << arr << endl;

    //     string str = GenerateRandString(10);
    //     cout << str << endl;

    //     ListNode* l = GenerateLinkedList(5);
    //     cout << l << endl;
    // }

    void Test()
    {
        TreeNode *n = new TreeNode("1_2_3_#_#_4_#_#_#_");
        cout << n << endl;
    }
}

// 1. 两数之和
namespace _01
{
    vector<int> twoSum(vector<int> &nums, int target)
    {
        unordered_map<int, int> record;

        for (int i = 0; i < nums.size(); ++i)
        {
            if (record.find(target - nums[i]) != record.end())
                return vector<int>{i, record[target - nums[i]]};
            else
                record.insert(make_pair(nums[i], i));
        }
        return vector<int>();
    }

    void Test()
    {
        vector<int> nums = GenerateRandIntArr(10000);
        cout << twoSum(nums, 100) << endl;
    }
}

// 2. 爬楼梯
namespace _02
{
    int climbStairs(int n)
    {
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;

        int minusOne = 2;
        int minusTwo = 1;
        int res = 0;
        for (int i = 3; i <= n; ++i)
        {
            res = minusOne + minusTwo;
            minusTwo = minusOne;
            minusOne = res;
        }

        return res;
    }
}

// 3. 合并有序数组
namespace _03
{
    void merge(int *nums1, int nums1Size, int m, int *nums2, int nums2Size, int n)
    {
        int i = m - 1, j = n - 1, k = nums1Size - 1;
        while (i >= 0 && j >= 0)
        {
            if (nums1[i] > nums2[j])
                nums1[k--] = nums1[i--];
            else
                nums1[k--] = nums2[j--];
        }
        while (i >= 0)
            nums1[k--] = nums1[i--];
        while (j >= 0)
            nums1[k--] = nums2[j--];
    }
}

// 4. 移动零
namespace _04
{
    void moveZeroes(int *nums, int numsSize)
    {
        int fast = 0, slow = 0;
        for (; fast < numsSize; ++fast)
        {
            if (nums[fast] != 0)
                nums[slow++] = nums[fast];
        }
        for (; slow < numsSize; ++slow)
            nums[slow] = 0;
    }
}

// 5. 找到消失的元素
namespace _05
{
    vector<int> findDisappearedNumbers(vector<int> &nums)
    {
        vector<int> res;
        for (int i = 0; i < nums.size(); ++i)
        {
            int index = nums[i] > 0 ? nums[i] - 1 : -nums[i] - 1;

            if (nums[index] > 0)
                nums[index] *= -1;
        }

        for (int i = 0; i < nums.size(); ++i)
        {
            if (nums[i] > 0)
                res.push_back(i + 1);
        }

        return res;
    }
}

// 6. 合并有序链表
namespace _06
{
    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
    {
        ListNode dummyHead;
        ListNode *p1 = list1, *p2 = list2, *cur = &dummyHead;
        while (p1 != nullptr && p2 != nullptr)
        {
            if (p1->val <= p2->val)
            {
                cur->next = p1;
                p1 = p1->next;
            }
            else
            {
                cur->next = p2;
                p2 = p2->next;
            }
            cur = cur->next;
        }
        cur->next = p1 == nullptr ? p2 : p1;
        return dummyHead.next;
    }
}

// 7. 环形链表
namespace _07
{
    bool hasCycle(struct ListNode *head)
    {
        if (head == NULL || head->next == NULL)
            return false;
        ListNode *fast = head->next->next, *slow = head->next;
        while (fast != NULL && fast->next != NULL)
        {
            if (fast == slow)
                return true;
            fast = fast->next->next;
            slow = slow->next;
        }
        return false;
    }
}

// 11. 盛最多水的容器
namespace _11
{
    int maxArea(vector<int> &height)
    {
        int l = 0, r = height.size() - 1;
        int res = 0;
        while (l < r)
        {
            res = height[l] < height[r] ? ::max(res, (r - l) * height[l++]) : ::max(res, (r - l) * height[r--]);
        }
        return res;
    }

    void Test()
    {
        vector<int> height{1, 1};
        cout << maxArea(height) << endl;
    }
}

int main()
{
    _11::Test();
}